package com.leetcode.algorithm.y21.m07;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode-cn.com
 * 
 * (done)70. 爬楼梯
 * (done)746. 使用最小花费爬楼梯
 * 
 * @author jie.deng
 *
 */
public class MySolution0709 {
	
	/**
	 * (done)70. 爬楼梯 
	 * 假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
	 * 注意：给定 n 是一个正整数。
	 * 
	 * 示例 1： 输入： 2 输出： 2 
	 * 解释： 有两种方法可以爬到楼顶。 
	 * 1. 1 步 + 1 步 
	 * 2. 2 步
	 * 
	 * 示例 2： 
	 * 输入： 3 
	 * 输出： 3 
	 * 解释： 有三种方法可以爬到楼顶。 
	 * 1. 1 步 + 1 步 + 1 步 
	 * 2. 1 步 + 2 步 
	 * 3. 2 步 + 1 步
	 * 
	 * @param n
	 * @return
	 */
	public int climbStairs(int n) {
		// f(n) = f(n-1) + f(n-2)
		// 爬第n阶楼梯的方法数量，等于 2 部分之和:
		// 1. 爬上 n-1n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
		// 2. 爬上 n-2n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
		if (n == 1) {
			return 1;
		}
		int[] dp = new int[n+1];
		dp[0] = 1;
		dp[1] = 1;// n=1
		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
	
	/**
	 * (done)746. 使用最小花费爬楼梯
	 * 
	 * 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
	 * 
	 * 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
	 * 
	 * 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
	 * 
	 * 示例 1:
	 * 
	 * 输入: cost = [10, 15, 20]
	 * 输出: 15
	 * 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
	 *  示例 2:
	 * 
	 * 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
	 * 输出: 6
	 * 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
	 * 注意：
	 * 
	 * cost 的长度将会在 [2, 1000]。
	 * 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * @param cost
	 * @return
	 */
	public int minCostClimbingStairs(int[] cost) {
		// f(n) = Math.min(f(n-1), f(n-2)) + cost[n]
		int len = cost.length;
		int[] dp = new int[len + 1];
		dp[0] = 0;
		dp[1] = 0;
		for (int i = 2; i <= len; i++) {
			dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
		}
		return dp[len];
	}
	
	
    /**
     * 78. 子集
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     * 
     * 示例:
     * 输入: nums = [1,2,3]
     * 输出:
     * [
     *   [3],
     *   [1],
     *   [2],
     *   [1,2,3],
     *   [1,3],
     *   [2,3],
     *   [1,2],
     *   []
     * ]
     * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/subsets
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param nums
     * @return
     */
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		int len = nums.length;
		for (int i = 0; i < (1 << len); i++) { // i从0到(2的len次方-1)
			List<Integer> subList = new ArrayList<Integer>(len);
			for (int j = 0; j < len; j++) {
				if ((i & (1 << j)) != 0) { // i的二进制表示哪一位为1则加入到subList
					subList.add(nums[j]);
				}
			}
			list.add(subList);
		}
		return list;
	}	
}
